{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Hash Tables\n",
    "\n",
    "\n",
    "\n",
    "## 1 Plant Information System\n",
    "\n",
    "\n",
    "### 1.1 OSISoft PI\n",
    "\n",
    "[OSISoft PI System](https://www.osisoft.cn/)\n",
    "\n",
    "The PI System enables digital transformation through trusted, high-quality operations data. Collect, enhance, and deliver data in real time in any location. Empower engineers and operators. Accelerate the work of analysts and data scientists. Support new business opportunities.\n",
    "\n",
    "PI System 通过可信的高质量运营数据实现数字化转型。在任何位置实时收集、增强和提供数据。为工程师和操作员提供支持。加快分析师和数据科学家的工作。支持新的业务机会。\n",
    "\n",
    "![](./img/ds/osisoft.png)\n",
    "\n",
    "Each analysis task needs to **search** the measuring points：\n",
    "\n",
    "\n",
    "* <p style=\"font-size:20px; color:blue\">A few or dozens of measuring points are taken from tens of thousands of measuring points.</p>\n",
    "\n",
    "### 1.2 Building Energy  Management System \n",
    "\n",
    "![](./img/ds/buildingsystem.png)\n",
    "\n",
    "![](./img/ds/buildingcode.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### 1.3  The Simple Example: Measurement Tags of VCC\n",
    "\n",
    "The table store the Measurement Tags of VCC,every the Tag recored has the uniqe tagID\n",
    "\n",
    "Refrigerant 134a is the working fluid in an ideal vapor-compression refrigeration cycle that\n",
    "communicates thermally with a cold region at 0°C and a warm region at 26°C. \n",
    "\n",
    "Saturated vapor enters the compressor at 0°C and saturated liquid leaves the condenser at 26°C.\n",
    "\n",
    "The mass flow rate of the refrigerant is 0.08 kg/s.\n",
    "\n",
    "\n",
    "\n",
    "![](./img/vcr/ivcr-ts.jpg)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%file ./data/VCC1_Tag.csv\n",
    "TagID,Tag,Desc,Unit,Value\n",
    "600,CompressorIPortM,压缩机入口流量,kg/s,0.08\n",
    "616,CompressorOPortP,压缩机出口压力,MPa,0.6854\n",
    "613,CompressorOPortT,压缩机出口温度,°C,29.27\n",
    "714,CondenserOPortT,冷凝器出口温度,°C,26\n",
    "708,CondenserOPortX,冷凝器出口干度,-,0\n",
    "814,ExpansionValveOPortT,膨胀阀出口温度,°C,26\n",
    "808,ExpansionValveOPortX,膨胀阀出口干度,°C,0\n",
    "914,EvaporatorValveOPortT,蒸发器出口温度,°C,0\n",
    "908,EvaporatorValveOPortX,蒸发器出口干度,-,1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Data Stucture of Tags**\n",
    "\n",
    "```python\n",
    "\n",
    "tag=(id,(tag,desc,value)) # tuple \n",
    "\n",
    "VCC1_TagTable=[]  # list\n",
    "\n",
    "VCC1_TagTable=[(id,(tag,desc,unit,value)),...]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import  csv\n",
    "filename=\"./data/VCC1_Tag.csv\"\n",
    "csvfile = open(filename, 'r',encoding=\"utf-8\")\n",
    "csvdata = csv.DictReader(csvfile)\n",
    "VCC1_TagTable=[]\n",
    "for line in csvdata:\n",
    "    id = int(line['TagID']) # convert to int\n",
    "    tag=line['Tag']\n",
    "    desc=line['Desc']\n",
    "    unit=c=line['Unit']\n",
    "    value=float(line['Value'])\n",
    "    VCC1_TagTable.append((id,(tag,desc,unit,value)))\n",
    "csvfile.close()  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "for item in  VCC1_TagTable:\n",
    "    print(item)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Get the tags of Compressor through tagID by the Linear Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "CompressorTagIDList=[600,616,614,914,908]\n",
    "for tagid in CompressorTagIDList:\n",
    "    for item in VCC1_TagTable:\n",
    "        if tagid==item[0]:\n",
    "            print(item[1])       "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Linear Search will perform  $𝑂(N)$  \n",
    "\n",
    "Here are the data structures, the complexities of their key lookup operations:\n",
    "\n",
    "| Data structure   |  lookup  |\n",
    "| ----------------- |:--------:|\n",
    "| Array         |  O(N)    |\n",
    "| Sorted array    |   O(logN) |\n",
    " \n",
    "If there is a data structure that can do better. And it turns out that there is: **the hash table**, one of the best and most useful data structures \n",
    "\n",
    "In Python, the type <font color=\"blue\">dict</font> dictionaries use <b>hashing</b> to do <b>the lookup in time</b> \n",
    "\n",
    "* that is nearly `independent` of the `size` of the dictionary\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The basic idea behind hashing is\n",
    "\n",
    "* **convert the key to an integer, and then use that integer to index into a list**\n",
    "\n",
    "which can be done in `constant` time. \n",
    "\n",
    "**Hash functions** : any function that can be used to map data of `arbitrary` size to `fixed-size` values.\n",
    "\n",
    "* `CurTagID%ListSize`(除留余数法 k mod m - 关键字k除以表长度m的余数)\n",
    "![](./img/ds/hash1.png)\n",
    "\n",
    "**Hash value** : The values returned by a hash function are called \n",
    "    \n",
    "* `Index_TagID=CurTagID%ListSize`\n",
    "\n",
    "**Hash table**: the data structure that maps keys to values with hashing\n",
    "\n",
    "* `VCC1_TagTable=[None for i in range(ListSize)]`\n",
    "\n",
    ">散列表通过把`关键码`值映射到表中`一个位置`来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表 \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For example we use the remainder `key%ListSize` as the index into the list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import  csv\n",
    "filename=\"./data/VCC1_Tag.csv\"\n",
    "csvfile = open(filename, 'r',encoding=\"utf-8\")\n",
    "csvdata = csv.DictReader(csvfile)\n",
    "\n",
    "# set the size of the store list\n",
    "ListSize=30;\n",
    "# the store table \n",
    "VCC1_TagTable=[None for i in range(ListSize)]\n",
    "for line in csvdata:\n",
    "    id = int(line['TagID'])\n",
    "    tag=line['Tag']\n",
    "    desc=line['Desc']\n",
    "    unit=line['Unit']\n",
    "    value=float(line['Value'])\n",
    "    # convert the key to an integer:  address in the list\n",
    "    address= id%ListSize\n",
    "    # put the record in the address of the list\n",
    "    VCC1_TagTable[address]=(id,(tag,desc,unit,value))\n",
    "    print(id,address)\n",
    "csvfile.close() "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for  i,item in  enumerate(VCC1_TagTable):\n",
    "    print(i,item)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Search one tag from TagID with the `unique` Index_TagID\n",
    "\n",
    "* It is done in **constant** time that is `independent` of the `size` of VCC1_TagList\n",
    "\n",
    "The complexity is $O(1)$\n",
    "\n",
    "* 如果每个关键字保留一个位置，就可以**直接寻址**，时间复杂度是O(1)。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "CompressorTagIDList=[600,616,613,914,908]\n",
    "for tagid in CompressorTagIDList:\n",
    "    address=tagid%ListSize\n",
    "    print(address,VCC1_TagTable[address])   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2 Collision \n",
    "\n",
    "### 2.1 Collision \n",
    "\n",
    "If the space of possible `outputs` is **smaller** than the space of possible `inputs`, \n",
    "\n",
    "* a hash function is a `many`-to-`one` mapping. \n",
    "\n",
    "the different keys are mapped to the same hash value,it is called a <b>collision</b>. \n",
    "\n",
    ">散列冲突：在散列表中，不同的关键字值对应到同一个存储位置的现象\n",
    "\n",
    "\n",
    "**For exmple**\n",
    "\n",
    "* the input sizes of key is :9\n",
    "\n",
    "* the output sizes of hash value:ListSize is 5\n",
    "\n",
    "The hash function : `id%ListSize`\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import  csv\n",
    "filename=\"./data/VCC1_Tag.csv\"\n",
    "csvfile = open(filename, 'r',encoding=\"utf-8\")\n",
    "csvdata = csv.DictReader(csvfile)\n",
    "\n",
    "# set the size of the store list\n",
    "ListSize=5;\n",
    "# the store table \n",
    "for line in csvdata:\n",
    "    id = int(line['TagID'])\n",
    "    # convert the key to an integer: address of the list\n",
    "    address= id%ListSize\n",
    "    print(id,address)\n",
    "csvfile.close()  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Many Collision!**\n",
    "```\n",
    "613 3\n",
    "708 3\n",
    "808 3\n",
    "908 3\n",
    "```\n",
    "```\n",
    "714 4\n",
    "814 4\n",
    "914 4\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**If Collision**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import  csv\n",
    "filename=\"./data/VCC1_Tag.csv\"\n",
    "csvfile = open(filename, 'r',encoding=\"utf-8\")\n",
    "csvdata = csv.DictReader(csvfile)\n",
    "\n",
    "# set the size of the store list\n",
    "ListSize=5;\n",
    "# the store table \n",
    "VCC1_TagTable=[None for i in range(ListSize)]\n",
    "for line in csvdata:\n",
    "    id = int(line['TagID'])\n",
    "    tag=line['Tag']\n",
    "    desc=line['Desc']\n",
    "    unit=line['Unit']\n",
    "    value=float(line['Value'])\n",
    "    # convert the key to an integer:address of the list\n",
    "    address= id%ListSize\n",
    "    # put the record in the index of the list\n",
    "    VCC1_TagTable[address]=(id,(tag,desc,unit,value))\n",
    "csvfile.close() "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "CompressorTagIDList=[600,616,613,914,908]\n",
    "for tagid in CompressorTagIDList:\n",
    "    address=tagid%ListSize\n",
    "    print(VCC1_TagTable[address]) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "you will see \n",
    "```\n",
    "(908, ('EvaporatorValveOPortX', '蒸发器出口干度', '-', 1.0))\n",
    "(908, ('EvaporatorValveOPortX', '蒸发器出口干度', '-', 1.0))\n",
    "```\n",
    "because the Collision \n",
    "```\n",
    "613 3\n",
    "708 3\n",
    "808 3\n",
    "908 3\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If the space of possible outputs is bigger than the space of possible inputs\n",
    "\n",
    "* **no collisions**?\n",
    "\n",
    "For example: `ListSize=20`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import  csv\n",
    "filename=\"./data/VCC1_Tag.csv\"\n",
    "csvfile = open(filename, 'r',encoding=\"utf-8\")\n",
    "csvdata = csv.DictReader(csvfile)\n",
    "\n",
    "# set the size of the store list\n",
    "ListSize=20;\n",
    "# the store table \n",
    "VCC1_TagTable=[None for i in range(ListSize)]\n",
    "for line in csvdata:\n",
    "    id = int(line['TagID'])\n",
    "    tag=line['Tag']\n",
    "    desc=line['Desc']\n",
    "    unit=line['Unit']\n",
    "    value=float(line['Value'])\n",
    "    # convert the key to an integer: address of the list\n",
    "    address= id%ListSize\n",
    "    # put the record in the index of the list\n",
    "    VCC1_TagTable[address]=(id,(tag,desc,unit,value))\n",
    "    print(id, address)\n",
    "csvfile.close() "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**collisions**\n",
    "\n",
    "```\n",
    "714 14\n",
    "814 14\n",
    "914 14\n",
    "\n",
    "708 8\n",
    "808 8\n",
    "908 8\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 Handle the collision \n",
    "\n",
    "The paths to handle the collision in Hash Table\n",
    "\n",
    "1. **minimizes collisions**: \n",
    "\n",
    "   * the `good` hash function： produces : **uniform distribution** every output in the range is equally probable, which `minimizes` the probability of `collisions`(散列函数设计要点:均匀性好,减少元素冲突次数)\n",
    "    \n",
    "  *  the `sweet spot` size of hash table\n",
    "\n",
    "\n",
    "2. **collision resolution**: Separate Chainingg(分离链接法), Open Addressing(开放地址法） \n",
    "\n",
    "\n",
    "### 2.3 Choice of hash table size\n",
    "\n",
    "Assuming you have a good hash function, by making the hash table large enough,\n",
    "\n",
    "Let’s think about the extremes:\n",
    "\n",
    "* You create a hash table with 1,000,000 buckets and you add 1,000 items to it. The chances of a collision are extremely low, and this will perform amazingly.\n",
    "\n",
    "we can **reduce** the number of collisions sufficiently to allow us to treat the complexity as O(1).\n",
    "\n",
    "* 一个足够大的数组，**可以**为每个关键字保留一个位置，就可以**直接寻址**，时间复杂度是O(1)。\n",
    "\n",
    "It will **waste a lot of space**. Therefore, you need to find the `“sweet spot”` for the size of the hash table vs. the number of items you plan to put into it. \n",
    "\n",
    "Choice of hash table size depends in part on choice of hash function, and collision resolution strategy\n",
    "\n",
    "But a good general **rule of thumb** is:\n",
    "\n",
    "* The hash table should be an array with length about **1.3** times the maximum number of keys that will actually be in the table, and\n",
    "Size of hash table array should be a **prime** number\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3 Separate Chaining\n",
    "\n",
    "### 3.1 Separate Chaining(分离链接法)\n",
    "There are different ways through which a collision can be resolved. We will look at a method called **Separate Chaining(分离链接法)**, \n",
    "\n",
    "**Chain hashing** avoids collision. The idea is to make each cell of hash table point to a linked list of records(`bucket`) that have same hash function value.\n",
    "\n",
    "* 将散列到同一个值的所有元素保留到一个`链表`中\n",
    "\n",
    "**bucket(桶)**:  a linked list of records with same hash function value\n",
    "\n",
    "The hash table is a list of `hash buckets`. \n",
    "\n",
    "For Example:\n",
    "```\n",
    "keys :   [36,18,72,43,6,10,5,15]\n",
    "tab size : 8\n",
    "hash function : key % tab size\n",
    "```\n",
    "![](./img/ds/hashtable_separatechaining.gif)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### 3.2 Hash Table in Python\n",
    "\n",
    "The basic idea is to represent the hash table by a list where **each item** is a list of **key/value** pairs that have the `same` hash index\n",
    "\n",
    "```python\n",
    "[\n",
    "\n",
    "    [bucket of the same hash value1],\n",
    "\n",
    "    [bucket of the same hash value2]\n",
    ",...\n",
    "]\n",
    "```\n",
    "\n",
    "the every key/value pair in bucket is the tuple:\n",
    "```python\n",
    "(key, value)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "keyvalues = [(36, \"赵\"), (18, \"钱\"), (72, \"孙\"), (43, \"李\"), (6, \"周\"), (10, \"吴\"), (5, \"郑\"), (15, \"王\")]\n",
    "num_buckets=8\n",
    "\n",
    "buckets=[[] for i in range(num_buckets)]\n",
    "\n",
    "print(\"Key\",\"The address in buckets\",\"\\n\"+20*\"-\")\n",
    "for item in keyvalues:\n",
    "    #hash function: key % num_buckets\n",
    "    address= item[0] % num_buckets\n",
    "    buckets[address].append(item)\n",
    "    print(item[0],address)\n",
    "\n",
    "print(\"\\nNo.\",\"Bucket\",\"\\n\"+20*\"-\")   \n",
    "for  i,bucket in  enumerate(buckets):\n",
    "    print(i,bucket)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3 Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "key=10\n",
    "hashvalue=key % num_buckets\n",
    "for item in buckets[hashvalue]:\n",
    "    if item[0]==key:\n",
    "        print(key,item[1])  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4 The Class of Separate Chaining\n",
    "\n",
    "* **key** is integer or string\n",
    "\n",
    "* **hash function**: Key % numBuckets and djb2 \n",
    "\n",
    "> Hash function for string\n",
    ">\n",
    ">* http://www.cse.yorku.ca/~oz/hash.html\n",
    ">\n",
    ">**djb2**\n",
    ">\n",
    ">This algorithm (k=33) was first reported by `Dan Bernstein` many years ago in comp.lang.c.\n",
    ">\n",
    ">The magic of number 33 (why it works better than many other constants, prime or not) has never been adequately explained.\n",
    ">```python\n",
    "> hash = 5381\n",
    "> for c in dictKey:\n",
    ">     hash = ((hash *33) + hash) + ord(c)\n",
    "> hash % numBuckets\n",
    ">```\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class hashTable:\n",
    "    \"\"\"A dictionary with integer and string keys\"\"\"\n",
    "    \n",
    "    def __init__(self, numBuckets):\n",
    "        \"\"\"Create an empty dictionary\n",
    "           buckets is initialized to a list of numBuckets empty lists.\n",
    "        \"\"\"\n",
    "        self.numBuckets=numBuckets\n",
    "        self.buckets=[[] for i in range(self.numBuckets)] \n",
    "            \n",
    "    def getHashValue(self, dictKey):\n",
    "        if isinstance(dictKey, int):\n",
    "            return dictKey % self.numBuckets\n",
    "        if isinstance(dictKey,str):\n",
    "            # djb2 hash algorithm by Dan Bernstein\n",
    "            hash = 5381\n",
    "            for c in dictKey:\n",
    "                hash = ((hash *33) + hash) + ord(c)\n",
    "            return hash % self.numBuckets\n",
    "\n",
    "    \n",
    "    def addEntry(self, dictKey, dictVal):\n",
    "        \"\"\"Assumes dictKey an int.  Adds an entry.\"\"\"\n",
    "        hashBucket = self.buckets[self.getHashValue(dictKey)]\n",
    "        for i in range(len(hashBucket)):\n",
    "            if hashBucket[i][0] == dictKey:\n",
    "                hashBucket[i] = (dictKey, dictVal) #if one was found,replace\n",
    "                return\n",
    "        hashBucket.append((dictKey, dictVal)) # append a new entry (dictKey, dictVal) to the bucket if none was found.\n",
    "        \n",
    "    def getValue(self, dictKey):\n",
    "        \"\"\"Returns entry associated with the key dictKey\"\"\"\n",
    "        hashBucket = self.buckets[self.getHashValue(dictKey)]\n",
    "        for e in hashBucket:\n",
    "            if e[0] == dictKey: # key\n",
    "                return e[1]     # the tuple of value \n",
    "        return None\n",
    "    \n",
    "    def __str__(self):\n",
    "        result = '{'\n",
    "        for b in self.buckets:\n",
    "            for e in b:\n",
    "                result = result + str(e[0]) + ':' + str(e[1]) + ','\n",
    "        return result[:-1] + '}' #result[:-1] omits the last comma"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### 4.1  Init the hash table\n",
    "\n",
    "```python\n",
    "def __init__(self, numBuckets):\n",
    "   \"\"\"\n",
    "   The instance variable buckets is initialized to a list of numBuckets empty lists\n",
    "   \"\"\"\n",
    "        self.numBuckets = numBuckets\n",
    "        self.buckets=[[] for i in range(self.numBuckets)] \n",
    "```\n",
    "\n",
    "### 4.2  hash function\n",
    "\n",
    "```python\n",
    "def getHashValue(self, dictKey):\n",
    "        if isinstance(dictKey, int):\n",
    "            return dictKey % self.numBuckets\n",
    "        if isinstance(dictKey,str):\n",
    "            # djb2 hash algorithm by Dan Bernstein\n",
    "            hash = 5381\n",
    "            for c in dictKey:\n",
    "                hash = ((hash *33) + hash) + ord(c)\n",
    "            return hash % self.numBuckets\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### 4.3 addEntry\n",
    "\n",
    "By making each bucket a list, we handle collisions by storing all of the values that hash to the same bucket in the list</b>. \n",
    "\n",
    "```python\n",
    "def addEntry(self, dictKey, dictVal):\n",
    "    \"\"\"\n",
    "     To store or look up an entry with key **dictKey\n",
    "    \"\"\" \n",
    "    hashBucket = self.buckets[self.getHashValue(dictKey)] # hashing the location `hashBucket` list in  the list of self.buckets \n",
    "    for i in range(len(hashBucket)):\n",
    "        if hashBucket[i][0] == dictKey:# the item in each bucket is tuple: (dictKey, dictVal)\n",
    "            hashBucket[i] = (dictKey, dictVal) #if one was found,replace\n",
    "            return\n",
    "         hashBucket.append((dictKey, dictVal)) # append a new entry (dictKey, dictVal) to the bucket if none was found.\n",
    "```      \n",
    "   \n",
    "we use the hash function  to convert dictKey into an integer, \n",
    "```python  \n",
    " hashBucket = self.buckets[self.getHashValue(dictKey)] # hashing the location `hashBucket` list in  the list of self.buckets \n",
    "```    \n",
    "and use that integer to index into buckets \n",
    "```python\n",
    "   hashBucket[i]\n",
    "```\n",
    "to find the hash bucket associated with **dictKey**: if <b>a value is to be stored</b>,then  \n",
    "\n",
    "* if one was found:  <b>replace</b> the value in the existing entry,  \n",
    "\n",
    "* if none was found: <b>append</b> a new entry to the bucket\n",
    "\n",
    "\n",
    "### 4.4 getValue\n",
    "\n",
    "```python \n",
    "\n",
    "def getValue(self, dictKey)\n",
    "```\n",
    "We then search that bucket (which is a list) linearly to see if there is an entry with the key dictKey.\n",
    "\n",
    "```python \n",
    " for e in hashBucket:\n",
    "            if e[0] == dictKey: // key\n",
    "                return e[1]     // value\n",
    "```\n",
    "\n",
    "If we are doing <b>a lookup</b> and there is an entry with the key, we simply return the value stored with that key. \n",
    "\n",
    "If there is no entry with that key, we return None. \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.5 Measurement Tags of VCC\n",
    "\n",
    "#### 4.5.1 Integer keys\n",
    "The hash table for Measurement Tags of VCC\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import  csv\n",
    "filename=\"./data/VCC1_Tag.csv\"\n",
    "csvfile = open(filename, 'r',encoding=\"utf-8\")\n",
    "csvdata = csv.DictReader(csvfile)\n",
    "Entrys=[]\n",
    "for line in csvdata:\n",
    "    id = int(line['TagID'])\n",
    "    tag=line['Tag']\n",
    "    desc=line['Desc']\n",
    "    unit=line['Unit']\n",
    "    value=float(line['Value'])\n",
    "    Entrys.append((id,(tag,desc,unit,value))) \n",
    "csvfile.close()  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**hash table smaller sise ,collisions**\n",
    "\n",
    "* numBucket=5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "numBuckets=5\n",
    "# numBuckets 5 <entries \n",
    "D = hashTable(numBuckets)\n",
    "for item in Entrys:\n",
    "    D.addEntry(item[0],item[1])\n",
    "\n",
    "print('The hashTable(integer key) is:')\n",
    "print(D)\n",
    "\n",
    "print('\\n', 'The hase buckets are:')\n",
    "for i,hashBucket in enumerate(D.buckets):\n",
    "    print('BucketID',i,'  ', hashBucket)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**one, two, or three tuples** depending upon <b>the number of collisions</b> that occurred"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "CompressorTagIDList=[600,616,613,914,908]\n",
    "for tagid in CompressorTagIDList:\n",
    "    thebucket=D.getValue(tagid)   \n",
    "    print(tagid,thebucket)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tagid=808\n",
    "thebucket=D.getValue(tagid)  \n",
    "print(tagid,thebucket)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 4.5.2 String keys"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import  csv\n",
    "filename=\"./data/VCC1_Tag.csv\"\n",
    "csvfile = open(filename, 'r',encoding=\"utf-8\")\n",
    "csvdata = csv.DictReader(csvfile)\n",
    "Entrys=[]\n",
    "for line in csvdata:\n",
    "    tag=line['Tag']\n",
    "    desc=line['Desc']\n",
    "    unit=line['Unit']\n",
    "    value=float(line['Value'])\n",
    "    Entrys.append((tag,(desc,unit,value))) \n",
    "csvfile.close()  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "numBuckets=5\n",
    "# numBuckets 5 <entries 10\n",
    "D = hashTable(numBuckets)\n",
    "for item in Entrys:\n",
    "    D.addEntry(item[0],item[1])\n",
    "\n",
    "print('The hashTable(String key) is:')\n",
    "print(D)\n",
    "\n",
    "print('\\n', 'The hase buckets are:')\n",
    "for i,hashBucket in enumerate(D.buckets):\n",
    "    print('BucketID',i,'  ', hashBucket)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tagid='CompressorOPortP'\n",
    "thebucket=D.getValue(tagid)  \n",
    "print(tagid,thebucket)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.6 Analysis Example \n",
    "\n",
    "#### 4.6.1 Tags with StringID"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%file ./data/VCC_TagStringID.csv\n",
    "Tag,Desc,Unit,Value\n",
    "CompressorIPortM,压缩机入口流量,kg/s,0.08\n",
    "CompressorOPortP,压缩机出口压力,MPa,0.6854\n",
    "CompressorOPortT,压缩机出口温度,°C,29.27\n",
    "CondenserOPortT,冷凝器出口温度,°C,26\n",
    "CondenserOPortX,冷凝器出口干度,-,0\n",
    "ExpansionValveOPortT,膨胀阀出口温度,°C,26\n",
    "ExpansionValveOPortX,膨胀阀出口干度,°C,0\n",
    "EvaporatorValveOPortT,蒸发器出口温度,°C,0\n",
    "EvaporatorValveOPortX,蒸发器出口干度,-,1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import csv\n",
    "def tags_key_str(filename):\n",
    "    csvfile = open(filename, 'r', encoding=\"utf-8\")\n",
    "    csvdata = csv.DictReader(csvfile)\n",
    "    Entrys = []\n",
    "    for line in csvdata:\n",
    "        tag = line['Tag']\n",
    "        desc = line['Desc']\n",
    "        unit = line['Unit']\n",
    "        value = float(line['Value'])\n",
    "        Entrys.append((tag, (desc, unit, value)))\n",
    "    csvfile.close()\n",
    "    return Entrys"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Entrys= tags_key_str(\"./data/VCC_TagStringID.csv\")\n",
    "for item in Entrys:\n",
    "    print(item)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 4.6.2 hash_table \n",
    "\n",
    "* hash_table : return `value ` from (desc, unit, value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class hash_table(hashTable):\n",
    "\n",
    "    def getValue(self, dictKey):\n",
    "        \"\"\"Returns the value of entry associated with the key dictKey\"\"\"\n",
    "        hashBucket = self.buckets[self.getHashValue(dictKey)]\n",
    "        for e in hashBucket:\n",
    "            if e[0] == dictKey:  #  key\n",
    "                return e[1][2]   # the value :(desc, unit, value)\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def thehashtable(entrys):\n",
    "    numBuckets = 5\n",
    "    tagtable=hash_table(numBuckets)\n",
    "    for item in entrys:\n",
    "        tagtable.addEntry(item[0], item[1])\n",
    "    return tagtable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 4.6.3 Analysis module with TagID\n",
    "\n",
    "Class `Tag` to get data with `tagid`\n",
    "\n",
    "```python\n",
    "class Tag:\n",
    "    def __init__(self, tagid=None):\n",
    "        \"\"\" create the tag object\"\"\"\n",
    "        self.tagid = tagid\n",
    "        self.v = None\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import CoolProp.CoolProp as cp\n",
    "\n",
    "class Tag:\n",
    "    def __init__(self, tagid=None):\n",
    "        \"\"\" create the tag object\"\"\"\n",
    "        self.tagid = tagid\n",
    "        self.v = None\n",
    "\n",
    "class Port:\n",
    "    def __init__(self, dictPort):\n",
    "        \"\"\" create the Port object\"\"\"\n",
    "        self.__dict__.update({'p': Tag(), 't': Tag(), 'x': Tag(), 'mdot': Tag(), \"h\": Tag()})\n",
    "\n",
    "        self.GetTaglist=[]\n",
    "        for key in dictPort:\n",
    "            setattr(self,key,Tag(dictPort[key]))\n",
    "            self.GetTaglist.append(getattr(self,key))\n",
    "           \n",
    "    def get_state(self):\n",
    "        if self.t.v is not None and self.x.v is not None:\n",
    "            self.h.v = cp.PropsSI('H', 'T', self.t.v+273.15, 'Q',\n",
    "                                self.x.v, 'R134a')/1000\n",
    "        \n",
    "        if self.p.v is not None and self.t.v is not None:\n",
    "            self.h.v = cp.PropsSI('H', 'P', self.p.v*1.0e6, 'T',\n",
    "                                self.t.v+273.15, 'R134a')/1000\n",
    "\n",
    "class Compressor:\n",
    "    \"\"\" compression of the refrigerant\"\"\"\n",
    "\n",
    "    def __init__(self, dictDev,taghashtable):\n",
    "        \"\"\"  Initializes \"\"\"\n",
    "        self.taghashtable = taghashtable\n",
    "        self.iPort = Port(dictDev['iPort'])\n",
    "        self.oPort = Port(dictDev['oPort'])\n",
    "        self.Wc = None\n",
    " \n",
    "    def get_data(self):\n",
    "        \"\"\" get data from external data sources\"\"\"\n",
    "        for item in self.iPort.GetTaglist:\n",
    "            item.v = self.taghashtable.getValue(item.tagid)\n",
    "        for item in self.oPort.GetTaglist:\n",
    "            item.v = self.taghashtable.getValue(item.tagid)\n",
    "        \n",
    "    def cal_performance(self):\n",
    "        \"\"\"  energy   \"\"\"\n",
    "        self.iPort.get_state()\n",
    "        self.oPort.get_state()\n",
    "        self.Wc = self.iPort.mdot.v * (self.oPort.h.v - self.iPort.h.v)\n",
    "  \n",
    "    def __str__(self):\n",
    "        result = '\\nWc(kW): {:>.2f}'.format(self.Wc)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if __name__ == \"__main__\":\n",
    "    \"\"\"\n",
    "    'CompressorIPortM', '压缩机入口流量', 'kg/s', 0.08)\n",
    "    'CompressorOPortP', '压缩机出口压力', 'MPa', 0.6854)\n",
    "    'CompressorOPortT', '压缩机出口温度', '°C', 29.27)\n",
    "    'EvaporatorValveOPortT', '蒸发器出口温度', '°C', 0.0)\n",
    "    'EvaporatorValveOPortX', '蒸发器出口干度', '-', 1.0)\n",
    "    \"\"\"\n",
    "    filename = \"./data/VCC_TagStringID.csv\"\n",
    "    entrys = tags_key_str(filename)\n",
    "    curTagTable = thehashtable(entrys)\n",
    "    \n",
    "    dictCompTags = {\"iPort\": {\"t\": 'EvaporatorValveOPortT',  \"x\": 'EvaporatorValveOPortX', \"mdot\": 'CompressorIPortM'},\n",
    "                    \"oPort\": {\"p\": 'CompressorOPortP', \"t\": 'CompressorOPortT'}\n",
    "                    }\n",
    "    curcomp = Compressor(dictCompTags, curTagTable)\n",
    "    curcomp.get_data()\n",
    "    curcomp.cal_performance()\n",
    "    print(curcomp)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5 Hash in C\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* key is integer\n",
    "* value is char\n",
    "\n",
    "### 5.1 intDict in C\n",
    "\n",
    "* intDict.h/c\n",
    "\n",
    "* mainintDict.c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%file ./demo/include/intDict.h\n",
    "#ifndef INTDICT_H\n",
    "#define INTDICT_H\n",
    "\n",
    "typedef struct _node\n",
    "{\n",
    "\tint key;\n",
    "\tchar value;\n",
    "\tstruct _node *next;\n",
    "} Node;\n",
    "\n",
    "typedef struct _hashtable\n",
    "{\n",
    "\tint numBuckets;\n",
    "\tNode **buckets; //the linked list stack\n",
    "} Hashtable;\n",
    "\n",
    "// Create hash table\n",
    "Hashtable *createHash(int numBuckets);\n",
    "\n",
    "// free hash table\n",
    "void *freeHash(Hashtable *hTable);\n",
    "\n",
    "// hash function for int keys\n",
    "int inthash(int key, int numBuckets);\n",
    "\n",
    "// Add Entry to table - keyed by int\n",
    "void addEntry(Hashtable *hTable, int key, char value);\n",
    "\n",
    "// Lookup  by int key\n",
    "Node *searchEntry(Hashtable *hTable, int key);\n",
    "\n",
    "// Get by int key\n",
    "char getValue(Hashtable *hTable, int key);\n",
    "\n",
    "#endif\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%file ./demo/src/intDict.c\n",
    "\n",
    "#include <stdio.h>\n",
    "#include <stdlib.h>\n",
    "#include \"intDict.h\"\n",
    "\n",
    "// Create hash table\n",
    "Hashtable *createHash(int numBuckets)\n",
    "{\n",
    "\tHashtable *table = (Hashtable *)malloc(sizeof(Hashtable *));\n",
    "\tif (!table)\n",
    "\t{\n",
    "\t\treturn NULL;\n",
    "\t}\n",
    "\n",
    "\ttable->buckets = (Node **)malloc(sizeof(Node) * numBuckets);\n",
    "\tif (!table->buckets)\n",
    "\t{\n",
    "\t\tfree(table);\n",
    "\t\treturn NULL;\n",
    "\t}\n",
    "\n",
    "\ttable->numBuckets = numBuckets;\n",
    "\t// initialize the head pointer of the bucket stack to NULL\n",
    "\tfor (int i = 0; i < table->numBuckets; i++)\n",
    "\t\ttable->buckets[i] = NULL;\n",
    "\n",
    "\treturn table;\n",
    "}\n",
    "\n",
    "void *freeHash(Hashtable *hTable)\n",
    "{\n",
    "\tNode *b, *p;\n",
    "\tfor (int i = 0; i < hTable->numBuckets; i++)\n",
    "\t{\n",
    "\t\tb = hTable->buckets[i];\n",
    "\t\twhile (b != NULL)\n",
    "\t\t{\n",
    "\t\t\tp = b->next;\n",
    "\t\t\tfree(b);\n",
    "\t\t\tb = p;\n",
    "\t\t}\n",
    "\t}\n",
    "\tfree(hTable->buckets);\n",
    "\tfree(hTable);\n",
    "}\n",
    "\n",
    "// hash function for int key\n",
    "int inthash(int key, int numBuckets)\n",
    "{\n",
    "\treturn key % numBuckets;\n",
    "}\n",
    "\n",
    "// Lookup by int key\n",
    "Node *searchEntry(Hashtable *hTable, int key)\n",
    "{\n",
    "\tNode *p;\n",
    "\tint addr = inthash(key, hTable->numBuckets);\n",
    "\tp = hTable->buckets[addr];\n",
    "\n",
    "\twhile (p && p->key != key)\n",
    "\t\tp = p->next;\n",
    "\n",
    "\treturn p;\n",
    "}\n",
    "\n",
    "// Add Entry to table - keyed by int\n",
    "void addEntry(Hashtable *hTable, int key, char value)\n",
    "{\n",
    "\tint addr;\n",
    "\tNode *p, *entry;\n",
    "\tp = searchEntry(hTable, key);\n",
    "\tif (p)\n",
    "\t{\n",
    "\t\treturn;\n",
    "\t}\n",
    "\telse\n",
    "\t{ /*\n",
    "          add a new item on the top of the linked list stack \n",
    "          and a pointer to the top element.  \n",
    "       */\n",
    "\t\taddr = inthash(key, hTable->numBuckets);\n",
    "\t\tentry = (Node *)malloc(sizeof(Node));\n",
    "\t\tentry->key = key;\n",
    "\t\tentry->value = value;\n",
    "\t\tentry->next = hTable->buckets[addr];\n",
    "\t\thTable->buckets[addr] = entry;\n",
    "\t}\n",
    "}\n",
    "\n",
    "// Get by int key\n",
    "char getValue(Hashtable *hTable, int key)\n",
    "{\n",
    "\tNode *p;\n",
    "\tp = searchEntry(hTable, key);\n",
    "\tif (p)\n",
    "\t{\n",
    "\t\treturn p->value;\n",
    "\t}\n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%file ./demo/src/mainintDict.c\n",
    "#include <stdio.h>\n",
    "#include <stdlib.h>\n",
    "#include <time.h>\n",
    "#include \"intDict.h\"\n",
    "\n",
    "int main()\n",
    "{\n",
    "\tint key[8]={36,18,72,43,6,10,5,15};\n",
    "\tchar value[8]={'A','B','C','D','E','F','G','H'};\n",
    "\n",
    "   \tint numBuckets = 8;\n",
    "\tint numEntries = 8;\n",
    "\tHashtable *hTable;\n",
    "\n",
    "\thTable = createHash(numBuckets);\n",
    "\tfor (int i = 0; i < numEntries; i++)\n",
    "\t{\n",
    "\t\taddEntry(hTable, key[i], value[i]);\n",
    "\t\tprintf(\"(%d %c)\\n\", key[i], value[i]);\n",
    "\t}\n",
    "\n",
    "\tprintf(\"\\nThe buckets(the linked list stack) are: \\n\");\n",
    "\tfor (int i = 0; i < hTable->numBuckets; i++)\n",
    "\t{\n",
    "\t\tNode *b, *p;\n",
    "\t\tb = hTable->buckets[i];\n",
    "\t\tprintf(\"bucket %d :\", i);\n",
    "\t\tif (b)\n",
    "\t\t{\n",
    "\t\t\tfor (p = b; p != NULL; p = p->next)\n",
    "\t\t\t\tprintf(\" (%d %c) \", p->key, p->value);\n",
    "\t\t\tprintf(\"\\n\");\n",
    "\t\t}\n",
    "\t\telse\n",
    "\t\t\tprintf(\"\\n\");\n",
    "\t}\n",
    "\n",
    "\tprintf(\"\\nHash search:\");\n",
    "    int curkey=18;\n",
    "    char curval = getValue(hTable,curkey);\n",
    "\tprintf(\"%d -> %c \\n\", curkey,curval);\n",
    "\n",
    "\tfreeHash(hTable);\n",
    "\treturn 0;\n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!gcc -o ./demo/bin/mainintDict ./demo/src/mainintDict.c ./demo/src/intDict.c -I./demo/include"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!.\\demo\\bin\\mainintDict "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###  5.2 The Linked list\n",
    "\n",
    "* add a new item on the top of the linked list(`Stack`)\n",
    "\n",
    "![](./img/ds/linked-list-stack.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%file ./demo/src/demoLinkedlist_stack.c\n",
    "#include <stdio.h>\n",
    "#include <stdlib.h>\n",
    "\n",
    "typedef struct _node\n",
    "{\n",
    "\tint val;\n",
    "\tstruct _node *next;\n",
    "} node;\n",
    "\n",
    "void push(node **head, int val)\n",
    "/* add a new item on the top of the linked list*/\n",
    "{\n",
    "\tnode *new_node=(node *)malloc(sizeof(node));\n",
    "\tnew_node->val = val;\n",
    "\tnew_node->next = *head;\n",
    "\t*head = new_node;\n",
    "}\n",
    "\n",
    "void print_list(node *head)\n",
    "{\n",
    "\tnode *current = head;\n",
    "\twhile (current != NULL)\n",
    "\t{\n",
    "\t\tprintf(\"%d\\n\", current->val);\n",
    "\t\tcurrent = current->next;\n",
    "\t}\n",
    "}\n",
    "\n",
    "int main()\n",
    "{\n",
    "\tnode *test_list = NULL;\n",
    "\tpush(&test_list, 8);\n",
    "\tpush(&test_list, 88);\n",
    "    push(&test_list, 98);\n",
    "\tprint_list(test_list);\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!gcc -o ./demo/bin/demoLinkedlist_stack ./demo/src/demoLinkedlist_stack.c "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!.\\demo\\bin\\demoLinkedlist_stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Adding an item to the end of the list(`queue`)\n",
    "\n",
    "\n",
    "![](./img/ds/linked-list-queue.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting ./demo/src/demoLinkedlist_queue.c\n"
     ]
    }
   ],
   "source": [
    "%%file ./demo/src/demoLinkedlist_queue.c\n",
    "#include <stdio.h>\n",
    "#include <stdlib.h>\n",
    "\n",
    "typedef struct _node\n",
    "{\n",
    "\tint val;\n",
    "\tstruct _node *next;\n",
    "} node;\n",
    "\n",
    "void push(node **head, node **tail, int val)\n",
    "/*Adding an item to the end of the list*/\n",
    "{\n",
    "\tnode *new_node  = (node *)malloc(sizeof(node));\n",
    "\tnew_node->val = val;\n",
    "\tnew_node->next = NULL;\n",
    "\tif (*head == NULL)\n",
    "\t{\n",
    "\t\t*head = new_node;\n",
    "        *tail=new_node;\n",
    "\t}\n",
    "\telse\n",
    "\t{\n",
    "        (*tail)->next = new_node;\n",
    "        *tail = new_node;\n",
    "    }\t\t\n",
    "}\n",
    "\n",
    "void print_list(node *head)\n",
    "{\n",
    "\tnode *current = head;\n",
    "\twhile (current != NULL)\n",
    "\t{\n",
    "\t\tprintf(\"%d\\n\", current->val);\n",
    "\t\tcurrent = current->next;\n",
    "\t}\n",
    "}\n",
    "\n",
    "int main()\n",
    "{\n",
    "\tnode *test_list = NULL;\n",
    "    node *tail = NULL;\n",
    "\n",
    "    push(&test_list, &tail, 8);\n",
    "    push(&test_list, &tail,88);\n",
    "    push(&test_list, &tail,98);\n",
    "    print_list(test_list);\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "!gcc -o ./demo/bin/demoLinkedlist_queue ./demo/src/demoLinkedlist_queue.c "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n",
      "88\n",
      "98\n"
     ]
    }
   ],
   "source": [
    "!.\\demo\\bin\\demoLinkedlist_queue "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.3 Unordered Map(C++11)\n",
    "\n",
    "Unordered maps are associative containers that store elements formed by the combination of a key value and a mapped value, and which allows for fast retrieval of individual elements based on their keys.\n",
    "\n",
    "In an unordered_map, the key value is generally used to uniquely identify the element, while the mapped value is an object with the content associated to this key. Types of key and mapped value may differ.\n",
    "\n",
    "Internally, the elements in the unordered_map are not sorted in any particular order with respect to either their key or mapped values, but organized into buckets depending on their hash values to allow for fast access to individual elements directly by their key values (with a constant average time complexity on average)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting ./demo/src/demo1_unordered_map.cpp\n"
     ]
    }
   ],
   "source": [
    "%%file ./demo/src/demo1_unordered_map.cpp\n",
    "\n",
    "#include <iostream>\n",
    "#include <string>\n",
    "#include <tuple>\n",
    "#include <unordered_map>\n",
    " \n",
    "using namespace std;\n",
    "typedef tuple<string,string,string,float> tupTag;\n",
    " \n",
    "int main()\n",
    "{  \n",
    "    unordered_map<int, tupTag> tags;\n",
    "    tags[600] =(tupTag){\"CompressorIPortM\",\"压缩机入口质量流量\",\"kg/s\",0.08 };\n",
    "    cout << \"Tag 600:  \" <<get<0>(tags[600]) <<\"\\t\"<< get<1>(tags[600])\n",
    "         << \"\\t\"<<get<2>(tags[600])<< \"\\t\"<<get<3>(tags[600])<<endl;\n",
    "    return 0;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "!g++ -fexec-charset=GBK -o ./demo/bin/demo1_unordered_map.exe ./demo/src/demo1_unordered_map.cpp "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tag 600:  CompressorIPortM\t压缩机入口质量流量\tkg/s\t0.08\n"
     ]
    }
   ],
   "source": [
    "!.\\demo\\bin\\demo1_unordered_map "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Further Reading\n",
    "\n",
    "* 严蔚敏，李冬梅，吴伟民. 数据结构（C语言版），人民邮电出版社（第2版）,2015年2月  \n",
    "\n",
    "* Mark Allen Weiss. Data Structures and Algorithm Analysis in C\n",
    "\n",
    "\n",
    "* [Redis: an in-memory database. The data model is key-value,](https://github.com/redis/redis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.7"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "304.475px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  },
  "widgets": {
   "state": {},
   "version": "1.1.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
